//--------------------------------------------------------------------
//
//  Laboratory 11                                          bstree.cpp
//
//  Iimplementation of the Binary Search Tree ADT
//   -- including the recursive partners of the 
//      public member functions
//
//--------------------------------------------------------------------
#include <new>
#include <stdexcept>
#include <iostream>
#include "bstree.h"

using namespace std;

// Constructor
template < class DT, class KF >
BSTreeNode<DT,KF>::BSTreeNode ( const DT &rootData,
         BSTreeNode<DT,KF> *leftPtr, BSTreeNode<DT,KF> *rightPtr )
{
    dataItem = rootData;
    left = leftPtr;
    right = rightPtr;
}

//--------------------------------------------------------------------

// Constructor
template < class DT, class KF >    // DT : tree data item
BSTree<DT,KF>::BSTree ()
              :root(NULL){};

// Destructor
template < class DT, class KF >
BSTree<DT,KF>::~BSTree ()
{
    clear();
}

// Binary search tree manipulation operations
// Insert data item
template < class DT, class KF >    
void BSTree<DT,KF>::insert ( const DT &newDataItem )
                    throw ( bad_alloc )        
{
    // Handle "full" exception
    if (isFull())                               
        throw bad_alloc();
    else
        insertSub( root, newDataItem );
}

template <class DT, class KF >
void BSTree<DT, KF>::insertSub
           ( BSTreeNode<DT,KF> *&nPtr, const DT &newDataItem )
{
    //Empty tree
    if (nPtr == NULL)                 
        nPtr = new BSTreeNode<DT,KF>(newDataItem,NULL,NULL);
    //Insert left
    else if (newDataItem.key() < nPtr->dataItem.key())       
        insertSub(nPtr->left, newDataItem);
    //Insert right
    else if (newDataItem.key() > nPtr->dataItem.key())       
        insertSub(nPtr->right, newDataItem);
    //Item existed
    else                                        
        nPtr->dataItem.setKey(newDataItem.key());
}

// Retrieve data item
template < class DT, class KF >    
bool BSTree<DT,KF>::retrieve ( KF searchKey, DT &searchData ) const
{
    return retrieveSub(root, searchKey, searchData);
}
 
template < class DT, class KF >    
bool BSTree<DT,KF>::retrieveSub(BSTreeNode<DT,KF> *nPtr,
                                KF searchKey, DT &searchData) const
{
    bool result;
    // Outside of the leaf, item not found
    if (nPtr == NULL)
        result = false;
    // Less than current, retrive left
    else if (searchKey < nPtr->dataItem.key() ){
        //cout << "less than " << nPtr->dataItem.key() <<", go left\n";
        result = retrieveSub(nPtr->left, searchKey, searchData);
    // Greater than current, retrive right
    }else if (searchKey > nPtr->dataItem.key() ){
        //cout << "greater than " << nPtr->dataItem.key() <<", go right\n";
        result = retrieveSub(nPtr->right, searchKey, searchData);
    // Else, item found
    }else
    {
        searchData = nPtr->dataItem;
        result = true;
    }
    return result;
}
                                                
// Remove data item
template < class DT, class KF >    
bool BSTree<DT,KF>::remove ( KF deleteKey )                  
{
    removeSub(root, deleteKey);
}

template < class DT, class KF >    
bool BSTree<DT,KF>::removeSub( BSTreeNode<DT,KF> *&nPtr, KF deleteKey )                  
{
    bool result;
    // Outside of the leaf, can not remove
    if (nPtr == NULL)
        result = false;
    // Less than current, recursively remove left
    else if (nPtr->dataItem.key() > deleteKey)
        result = removeSub(nPtr->left, deleteKey);
    // Greater than current, recursively remove right
    else if (nPtr->dataItem.key() < deleteKey)
        result = removeSub(nPtr->right, deleteKey);
    // Else, remove current node
    else{
        removeNode(nPtr);
        result = true;
    }
    return result;
}

template < class DT, class KF >    
bool BSTree<DT,KF>::removeNode ( BSTreeNode<DT,KF> *&nPtr )                  
{
    DT maxLeft;
    BSTreeNode<DT,KF> *tmpNode;
    tmpNode = nPtr;
    // If no left child, replace by right child
    if (nPtr->left == NULL)
    {
        nPtr = nPtr->right;
        delete tmpNode;
    }
    // If no right child, replace by left child
    else if(nPtr->right == NULL)
    {
        nPtr = nPtr->left;
        delete tmpNode;
    }
    // Both children existed, copy the dataItem of 
    // the largest in the left subtree
    else
    {
        findPrior(nPtr->left, maxLeft);
        nPtr->dataItem = maxLeft;
        removeSub(nPtr->left, maxLeft.key());
    }
    return true;
}

template < class DT, class KF >    
void BSTree<DT,KF>::findPrior (BSTreeNode<DT,KF> *nPtr, DT &data)                       
{
    while(nPtr->right != NULL)
        nPtr = nPtr->right;
    data = nPtr->dataItem;
}

// Output keys
template < class DT, class KF >    
void BSTree<DT,KF>::writeKeys () const                      
{
    writeSub(root);
}

template < class DT, class KF >    
void BSTree<DT,KF>::writeSub (BSTreeNode<DT,KF> *nPtr) const                      
{
    if (nPtr != NULL)
    {
        writeSub(nPtr->left);
        cout << nPtr->dataItem.key() << endl;
        writeSub(nPtr->right);
     }
}   

// Clear tree
template < class DT, class KF >    
void BSTree<DT,KF>::clear ()                                
{
    clearSub(root);
}

template < class DT, class KF >    
void BSTree<DT,KF>::clearSub (BSTreeNode<DT,KF> *&nPtr) const                      
{
    if (nPtr != NULL)
    {
        clearSub(nPtr->left);
        clearSub(nPtr->right);
        delete nPtr;
        nPtr = NULL;
    }
}   

// Binary search tree status operations
// Tree is empty
template < class DT, class KF >    
bool BSTree<DT,KF>::isEmpty () const                          
{
    return (root == NULL);
}

// Tree is full
template < class DT, class KF >    
bool BSTree<DT,KF>::isFull () const                            
{
    BSTreeNode<DT,KF>* tmpNode;
    try
    {
        DT tmpData;
        tmpNode = new BSTreeNode<DT,KF>(tmpData,NULL,NULL);
        delete tmpNode;
        return false;
    }catch(std::bad_alloc exception){
        return true;
    }
}

// Output the tree structure -- used in testing/debugging
//template < class DT, class KF >    
//void BSTree<DT,KF>::showStructure () const

#include "show11.cpp"


// In-lab operations
// Height of tree
template < class DT, class KF >    
int BSTree<DT,KF>::height () const                          
{
    int result = heightSub(root);
    return result;
}

template < class DT, class KF >    
int BSTree<DT,KF>::heightSub (BSTreeNode<DT,KF> *nPtr) const                          
{
    int result;
    if(nPtr==NULL)
        result = 0;
    else{
        int numL = heightSub(nPtr->left);
        int numR = heightSub(nPtr->right);
        if (numL > numR)
            result = numL + 1;
        else
            result = numR + 1;
    }
    return result;
}


// Output keys  < searchKey
template < class DT, class KF >    
void BSTree<DT,KF>::writeLessThan ( KF searchKey ) const    
{                                                  
    writeLSub(root, searchKey);
}

template < class DT, class KF >    
void BSTree<DT,KF>::writeLSub 
          ( BSTreeNode<DT,KF> *nPtr, KF searchKey ) const    
{                                                  
    if (nPtr!=NULL)
    {    
        if (nPtr->dataItem.key() >= searchKey)
            writeLSub(nPtr->left, searchKey);
        else
        {
            writeSub(nPtr->left);
            cout << nPtr->dataItem.key() << endl;
            writeLSub(nPtr->right, searchKey);
        }
    }
}

